Search for: All records

We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications. 

Abstract We use online data assimilation to combine information from a linear inverse model of coupled atmosphere‐ocean dynamics with proxy records to create a new annual‐resolution reconstruction of atmosphere and ocean fields over the last millennium. Instrumental validation of reconstructed sea‐surface temperature and 0–700 m ocean heat content shows broad regions of positive spatial correlations, and high correlations (∼0.6–0.9) for global averages and indices of large‐scale modes of atmospheric variability. Compared to previous reconstructions, the online reconstructions show global and hemispheric averages with little‐to‐no millennial‐scale trend and global‐mean temperatures ∼0.25–0.5 K cooler during early periods (1000–1400 C.E.). The spatial anomaly differences of average temperature between an early (1000–1250 C.E.) and later (1400–1700 C.E.) period show warm anomalies over high‐latitude Europe and cool tropical conditions in partial agreement with previous assessments. The addition of online data assimilation, which provides dynamical memory to climate proxy information, is shown to be crucial for adequately characterizing decadal‐to‐centennial‐scale variability of 0–700 m ocean heat content. Furthermore, the climate forecasts provide model‐based physical constraints for atmosphere–ocean interaction, which become increasingly important during early periods when less proxy information is available for assimilation.